from LinkedQueue import *


class Tree:
    """树类的基类，用于被其他子类继承，"""

    # ------------------------------内置位置类-----------------------------------
    class Position:
        """每一个支点都是一个位置"""

        def element(self):
            raise NotImplementedError('must be implemented by subclass')

        def __eq__(self, other):
            raise NotImplementedError('must be implemented by subclass')

        def __ne__(self, other):
            raise NotImplementedError('must be implemented by subclass')

    # ----------------------------抽象方法------------------------------------
    def root(self):
        raise NotImplementedError('must be implemented by subclass')

    def parent(self):
        raise NotImplementedError('must be implemented by subclass')

    def num_children(self,p):
        raise NotImplementedError('must be implemented by subclass')

    def children(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def __len__(self):
        raise NotImplementedError('must be implemented by subclass')

    def is_root(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def is_leaf(self, p):
        raise NotImplementedError('must be implemented by subclass')

    def is_empty(self):
        return len(self) == 0

    def depth(self, p):
        if self.is_root(p):
            return 0
        else:
            return 1 + self.depth(self.parent(p))

    def _height1(self):
        return max(self.depth(p) for p in self.position() if self.is_leaf(p))

    def _height2(self, p):
        if self.is_leaf(p):
            return 0
        else:
            return 1 + max(self._height2(c) for c in self.children(p))

    def __iter__(self):
        for p in self.position():
            yield p.element()

    def position(self):
        """使用中序遍历方法来迭代"""
        return self.inorder()

    # ---------------------------先序遍历----------------------------
    def preorder(self):
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):
                yield p

    def _subtree_preorder(self, p):
        yield p
        for c in self.children(p):
            for other in self._subtree_preorder(c):
                yield other

    # --------------------------后序遍历------------------------------
    def postorder(self):
        if not self.is_empty():
            for p in self._subtree_postorder(self.root()):
                yield p

    def _subtree_postorder(self, p):
        for c in self.children(p):
            for other in self._subtree_postorder(c):
                yield other
        yield p

    # ---------------------------广度优先遍历------------------------
    def breadthfirst(self):
        if not self.is_empty():
            fringe = LinkedQueue()
            fringe.enqueue(self.root())
            while not fringe.is_empty():
                p = fringe.dequeue()
                yield p
                for c in self.children(p):
                    fringe.enqueue(c)

    # -------------------------中序遍历------------------------------
    def inorder(self):
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

    def _subtree_inorder(self, p):
        if self.left(p) is not None:
            for other in self._subtree_inorder(self.left(p)):
                yield other

        yield p

        if self.right(p) is not None:
            for other in self._subtree_inorder(self.right(p)):
                yield other


if __name__ == '__main__':
    # 以下两个函数，ste_root()将p作为根节点重置tree
    def reserver_p(tree, p, parent):
        p.children = parent
        if tree.parent(parent) is not None:
            reserver_p(tree, parent, tree.parent(parent))
        parent.parent = p


    def set_root(tree,p):
        parent = tree.parent(p)
        if parent is not None:
            reserver_p(tree, p, parent)